#include <iostream>

using std::cout;
using std::endl;

int quickSort(int *arr, int i, int j)
{
    int val = arr[i];
    while(i < j){
        while(j > i && arr[j] >= val)
            j--;
        if(i < j)
            arr[i++] = arr[j];
        while(j > i && arr[i] <= val)
            i++;
        if(i < j)
            arr[j--] = arr[i];
    }

    arr[i] = val;
    return i;
}

void sort_(int *arr, int i, int j)
{
    if(i >= j) return;
    int pos = quickSort(arr, i, j);
    sort_(arr, i, pos - 1);
    sort_(arr, pos + 1, j);
}

void sort(int *arr, int len)
{
    sort_(arr, 0, len - 1);
    for(int i{}; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(int args, char *argv[])
{
    int arr[] = {6, 3, 8, 3, 8, 4, 0, 1, -5};
    int len = sizeof(arr) /sizeof(int);
    sort(arr, len);
    return 0;
}